package com.wang.utils.stack;

import com.sun.xml.internal.stream.StaxEntityResolverWrapper;

import javax.annotation.Resource;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author 10570
 * @date 2021/7/25 23:37
 */

public class PolandNotation {
    public static void main(String[] args) {
        //说明
        //1、  1+（（2+3）*4）-5  ==》 1 2 3 + 4 * + 5 -
        //2、 现将字符串转为ArrayList
        String expression = "1+((2+3)*4)-5";
        List<String> list = toInfixExpressionList(expression);
        System.out.println(list);
        //3、将中缀表达式转为后缀表达式  [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] 消除小括号
        List<String> list1 = parseSuffixExpression(list);
        System.out.println(list1);
        int calculate = calculate(list1);
        System.out.println(calculate);


      /*  //数字和符号用空格隔开
        //(3+4）* 5 -6   逆波兰表达式 3 4 + 5 * 6 -
        //(30+4）* 5 -6
        //4 * 5 - 8 + 60 + 8 / 2  => 76  表达式 4 5 * 8 - 60 + 8 2 / +
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
        //思路
        //1、将表达式放到arrayList中
        //2、将ArrayList传递给一个方法，遍历ArrayList，配合stack完成运算
        List<String> rpnList = getListString(suffixExpression);
        int calculate = calculate(rpnList);
        System.out.println(calculate);*/
    }

    public static List<String> parseSuffixExpression(List<String> list){
        //定义两个栈
        Stack<String> s1 = new Stack<>(); //符号栈
//        Stack<String> s2 = new Stack<>(); //中间结果栈 整个转换中没有进行出入栈操作，之后还要逆序输出，用ArrayList替代
        List<String> s2 = new ArrayList<>();
        for (String item: list) {
            //是数就加入s2
            if (item.matches("\\d+")){
                s2.add(item);
            }else if (item.equals("(")){
                s1.push(item);
            }else if (item.equals(")")){
                //如果是右括号，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号位置，此时一堆括号丢弃
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();//将小括号弹出
            }else {
                //优先级问题
                //item 优先级小于等于栈顶优先级时，将s1栈顶的运算符取出加入到s2，再次执行（4.1）与s1中断的栈顶运算符比较
                //缺优先级的高低
                while (s1.size() != 0 && Operation.getValue(s1.peek())>= Operation.getValue(item)){
                    s2.add(s1.pop());
                }
                //当前扫描的运算符 将item 压入栈
                s1.push(item);
            }
        }
        //将s1中的数加入到s2
        while (s1.size() != 0){
            s2.add(s1.pop());
        }
        return s2; //因为是依次加入的所有输出就是按序的
    }
    //将中缀表达式转为后缀表达式
    public static List<String> toInfixExpressionList(String expression){
        List<String> list = new ArrayList<>();
        int i = 0 ;//用于遍历中缀字符串
        String str ; //做对多位数的拼接
        char c ;//每遍历一个就放入c
        do{
            //如果c是非数字，就需要加入到list中
            if ((c=expression.charAt(i)) < 48 || (c= expression.charAt(i)) > 57){
                list.add(""+c);
                i++; //后移
            }else {
                //考虑多位数问题
                str = "";
                while (i < expression.length() && (c=expression.charAt(i)) >= 48 && (c= expression.charAt(i)) <= 57){
                    str += c; //拼接
                    i++;
                }
                list.add(str);
            }
        }while (i < expression.length());
        return list;
    }

    //将一个表达式依次放入到ArrayList中
    public static List<String> getListString(String suffixExpression){
        //将字符串分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String str: split){
            list.add(str);
        }
        return list;
    }

    //完成对逆波兰表达式的运算
    /**
     *        （1）从左至右扫描，将3和4压入堆栈；
    *         （2）遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
    *         （3）将5入栈；
    *         （4）接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
    *         （5）将6入栈；
    *         （6）最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
     */

    public static int calculate(List<String> ls){
        Stack<String> stack = new Stack<>();
        //遍历ls
        for (String str: ls
             ) {
            //使用正则表达式区出栈
            if (str.matches("\\d+")){ //匹配多位数
                stack.push(str);
            }else {
                //pop两个数运算，再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (str.equals("+")){
                    res = num1+num2;
                }else if (str.equals("-")){
                    res = num1-num2;
                }else if (str.equals("*")){
                    res = num1 * num2;
                }else if (str.equals("/")){
                    res = num1 / num2;
                }else {
                    throw new RuntimeException("yichang");
                }
                stack.push(res+"");
            }

        }

        return Integer.parseInt(stack.pop());
    }
}

//返回对应的优先级
class Operation{
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;
    //返回对应的优先级value
    public static int getValue(String operation){
        int result = 0;
        switch (operation){
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                break;
        }
        return result;
    }
}
